package algorithm.数据量猜解法;

import java.util.TreeMap;
import java.util.TreeSet;

public class SubsquenceMaxModM {

    public static int fun1(int[] arr, int m){
        int length = arr.length;
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        boolean[][] dp = new boolean[length][sum + 1];
        dp[0][arr[0]] = true;
        dp[0][0] = true;

        for (int i = 1; i < length; i++) {
            for (int j = 0; j < sum + 1; j++) {
                if(dp[i - 1][j])
                    dp[i][j] = true;
                else
                    if(j - arr[i] >= 0 && dp[i - 1][j - arr[i]])
                        dp[i][j] =  true;
            }
        }

        int max = 0;
        for (int i = 0; i < sum + 1; i++) {
            if(dp[length - 1][i])
                max = Math.max(max, i % m);
        }
        return max;
    }

    public static int fun2(int[] arr, int m){
        int length = arr.length;
        boolean[][] dp = new boolean[length][m];

        dp[0][arr[0] % m] = true;
        dp[0][0] = true;

        for (int i = 1; i < length; i++) {
            for (int j = 0; j < m; j++) {
                if(dp[i - 1][j])
                    dp[i][j] = true;
                else{
                    int s = arr[i] % m;
                    if(s <= j)
                        dp[i][j] = dp[i - 1][j - s];
                    else
                        dp[i][j] = dp[i -1][m + j - s];
                }
            }
        }

        int max = 0;
        for (int i = 0; i < m; i++) {
            if(dp[length - 1][i])
                max = i;
        }
        return max;
    }

    //分治，需要考虑将左右两个分支组合在一起的情况
    public static int fun3(int[] arr, int m){
        int length = arr.length;
        int mid = (length -  1) / 2;
        TreeSet<Integer> leftSet = new TreeSet<>();
        TreeSet<Integer> rightSet = new TreeSet<>();

        process(arr, 0, mid, m, 0, leftSet);
        process(arr, mid + 1, length - 1, m, 0, rightSet);

        int max = 0;
        for (Integer integer : leftSet) {
            Integer floor = rightSet.floor(m - 1 - integer);
            if(floor != null){
                max = Math.max(max, integer + floor);
            }
        }
        return max;
    }

    public static void process(int[] arr, int index, int end, int m, int sum, TreeSet<Integer> treeSet){
        if(index == end + 1){
            treeSet.add(sum % m);

        }else {
            process(arr, index + 1, end, m, sum, treeSet);
            process(arr, index + 1, end, m, sum + arr[index], treeSet);
        }

    }

    public static int[] generateRandomArray(int len, int value) {
        int[] ans = new int[(int) (Math.random() * len) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (int) (Math.random() * value);
        }
        return ans;
    }

    public static void main(String[] args) {
        int len = 10;
        int value = 100;
        int m = 76;
        int testTime = 500000;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(len, value);
            int ans1 = fun1(arr, m);
            int ans2 = fun2(arr, m);
            int ans3 = fun3(arr, m);
            if (ans1 != ans2 || ans2 != ans3) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish!");

    }





}
